package dataStructure.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lhn
 * @date 2024-09-01 16:21
 */

public class BinarySearch {
    public static void main(String[] args) {
//        int[] arr1 = {1, 8, 10, 89, 1000, 1234};
        int[] arr2 = {1, 8, 10, 1000, 1000, 1000, 1234};
//        System.out.println(binarySearch(arr1, 1000));
        System.out.println(binarySearchArrayList(arr2, 1000));
    }

    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    public static ArrayList binarySearchArrayList(int[] arr, int target) {
        ArrayList<Integer> ans = new ArrayList<>();
        int left = 0;
        int right = arr.length - 1;

        System.out.println("开始查找");

        while (left <= right) {
            int mid = (left + right) / 2;
            System.out.println("mid:" + mid);
            if (arr[mid] == target) {
                System.out.println("找到：" + mid);
                ans.add(mid);
                //查找值的左右两个是否是需要查找的值，防止修改mid的值
                int tempLeft = mid - 1;
                int tempRight = mid + 1;
                while (tempLeft > 0 && arr[mid - 1] == target) {
                    System.out.println("找到：" + tempLeft);
                    ans.add(tempLeft);
                    tempLeft--;
                }
                while (tempRight < arr.length - 1 && arr[mid + 1] == target) {
                    System.out.println("找到：" + tempRight);
                    ans.add(tempRight);
                    tempRight++;
                }
            }
            //向左边查找
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return ans;
    }
}
